#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void insert(stack<int> &stk, int val)
{
    if (stk.empty()) {stk.push(val); return;}
    if (stk.top() < val) {stk.push(val); return;}
    else {
	int top = stk.top();
	stk.pop();
	insert(stk, val);
	stk.push(top);
    }
}

void sortStk(stack<int> &stk)
{
    if (stk.empty()) return;
    int val = stk.top();
    stk.pop();
    sortStk(stk);
    insert(stk, val);
}

void insert1(stack<int> &stk, int val)
{
    if (stk.empty()) {stk.push(val); return;}
    if (stk.top() > val) {stk.push(val); return;}
    else {
	int top = stk.top();
	stk.pop();
	insert1(stk, val);
	stk.push(top);
    }
}

void sortStk1(stack<int> &stk)
{
    if (stk.empty()) return;
    int val = stk.top();
    stk.pop();
    sortStk1(stk);
    insert1(stk, val);
}

int main(int argc, char **argv)
{
    stack<int> stk;
    for (int i = 0; i < 10; i++) {
	int num = rand()%20;
	cout << num << " ";
	stk.push(num);
    }
    sortStk1(stk);
    cout << endl;
    while(!stk.empty()) {
	cout << stk.top() << " ";
	stk.pop();
    }
}
